package com.shangguigu.search;

import org.junit.Test;

import java.util.Arrays;

/**
 * @author: ZhouBert
 * @date: 2019/10/15
 * @description: 斐波那契查找算法 TODO:斐波那契查找的时间复杂度还是O(log 2 n )，但是 与折半查找相比，斐波那契查找的优点是它只涉及加法和减法运算，而不用除法，而除法比加减法要占用更多的时间，因此，斐波那契查找的运行时间理论上比折半查找小，但是还是得视具体情况而定。
 * 理论基础：
 * F(k)=F(k-1)+F(k-2)
 * 即
 * F(k)-1=F(k-1)-1+F(k-2)-1 +1
 * 可以看做 left~right 的距离为 F(k)-1 分段 F(k-1)-1 mid F(k-2)-1
 */
public class FibonacciSearch {
	public static int maxSize = 20;

	public static void main(String[] args) {
		int[] arr = {1, 8, 10, 89, 1000, 1234};
		System.out.println("index=" + fibSearch(arr, 1234));

	}

	/**
	 * 由于公式 mid=low+F(k-1)-1,需要使用斐波那契数列，所以先获取一个斐波那契数列
	 * 下面通过递归方式获取
	 *
	 * @return
	 */
	public static int[] fib() {
		int[] f = new int[maxSize];
		f[0] = 1;
		f[1] = 1;
		for (int i = 2; i < maxSize; i++) {
			f[i] = f[i - 1] + f[i - 2];
		}
		return f;
	}

	/**
	 * 编写斐波那契查找算法
	 * 迭代
	 *
	 * @param a
	 * @param key
	 * @return
	 */
	public static int fibSearch(int[] a, int key) {
		int low = 0;
		int high = a.length - 1;

		///表示斐波那契分割数值的下标
		int k = 0;
		///存放mid值
		int mid = 0;
		///获取斐波那契数列
		int f[] = fib();
		///获取斐波那契分割数值的下标
		while (high > f[k] - 1) {
			k++;
		}

		///构建斐波那契数组
		int[] temp = Arrays.copyOf(a, f[k]);
		for (int i = high + 1; i < temp.length; i++) {
			temp[i] = a[high];
		}

		while (low <= high) {
			mid = low + f[k - 1] - 1;
			if (key < temp[mid]) {
				high = mid - 1;
				k--;
			} else if (key > temp[mid]) {
				low = mid + 1;
				k -= 2;
			}
			///找到
			else {
				///todo:当斐波那契数列索引超出原数组时，high<mid
				if (mid <= high) {
					return mid;
				} else {
					return high;
				}
			}
		}
		return -1;
	}

	/**
	 * todo: f(k)-1 表示长度！
	 *
	 * @param nums
	 * @param key
	 * @return
	 */
	public static int fibSearchMine(int[] nums, int key) {
		int low = 0;
		int high = nums.length - 1;
		///表示中间分割点索引的位置
		int mid = 0;
///斐波那契数列索引
		int k = 0;
		///获取黄金分割数列
		int[] f = fib();
		///判断黄金分割的数量///知道黄金分割数量刚超出数列数量
//		while (f[k]<high){
//			k++;
//		}

		while (f[k] - 1 < high) {
			k++;
		}

		///补全到斐波那契的数目
		int[] newnums = Arrays.copyOf(nums, f[k]);
		for (int i = high + 1; i < f[k]; i++) {
			newnums[i] = nums[high];
		}

		while (low <= high) {
//			mid=low	+ f[k-1];
			mid = low + f[k - 1] -1;
			if (newnums[mid] > key) {
				high = mid - 1;
				k -= 2;
			} else if (newnums[mid] < key) {
				low = mid + 1;
				k--;
			} else {
				return Math.min(mid, high);
			}
		}
		return -1;
	}


	/**
	 * 测试我写的斐波那契
	 */
	@Test
	public void testFibSearchMine() {
		int[] arr = {1, 8, 10, 89, 1000, 1234};
		System.out.println("index=" + fibSearchMine(arr, 1));
	}

}
